package com.剑指Offer;

/*
 * 有两个排序的数组，在第一个数组的末尾有足够多的空余空间容纳第二个数组，把第二个数组的所有数字插入到第一个数组中
 * 并且保证所有的数字是排序的
 */
public class 合并两个排序数组 {
	public static void process(int[] shu1, int[] shu2, int shu1length) {
		int size = shu1length + shu2.length - 1;
		int index = size;
		int p1 = shu1length - 1;
		int p2 = shu2.length - 1;
		while (p1 >= 0 && p2 >= 0) {
			if (shu2[p2] >= shu1[p1]) {
				shu1[index] = shu2[p2];
				p2--;
				index--;
			} else {
				shu1[index] = shu1[p1];
				p1--;
				index--;
			}
		}
		if (p1 > 0) {
			while (p1 > 0) {
				shu1[index] = shu1[p1];
				p1--;
				index--;
			}
		}
		if (p2 > 0) {
			while (p2 > 0) {
				shu1[index] = shu2[p2];
				p2--;
				index--;
			}
		}
		for (int i = 0; i <= size; i++) {
			System.out.print(shu1[i] + "  ");
		}
	}
	public static void main(String[] args) {
		int shu[] = new int[30];
		int shu1[] = { 2, 2, 3, 5, 7, 8, 9, 23, 45 };
		System.arraycopy(shu1, 0, shu, 0, shu1.length);
		int shu2[] = { 4, 8, 13, 15, 23, 45, 67, 78 };
		process(shu, shu2, shu1.length);
	}
}
